package 动态规划;
//https://www.nowcoder.com/practice/ed2923e49d3d495f8321aa46ade9f873?tpId=46&tqId=29065&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
public class 不同的子序列 {
    public int numDistinct (String S, String T) {
        // write code here
        int[][] arr = new int[S.length() + 1][T.length() + 1];
        arr[0][0] = 1;
        for (int i = 1 ; i <= S.length() ; i ++){
            arr[i][0] = 1;
        }
        for (int i = 1 ; i <= T.length() ; i ++){
            arr[0][i] = 0;
        }
        for (int i = 1 ; i <= S.length() ; i ++){
            for (int j = 1 ; j <= T.length() ; j ++){
                if (S.charAt(i - 1) == T.charAt(j - 1)){
                    arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
                }else {
                    arr[i][j] = arr[i - 1][j];
                }
            }
        }
        return arr[S.length()][T.length()];

    }
}
